/**
 * @file   BalanceTree.h
 * @author WinterMelonCDY <wintermeloncdy@wintermeloncdy-VirtualBox>
 * @date   Fri Nov 19 21:24:57 2021
 * 
 * @brief  
 * 
 * 
 */

#include<iostream>
#include<algorithm>
#include<vector>

// template class of AVT tree
template<typename Comparable>
class AVLTree
{
    private:
    // Node struct with left and right children and constructor function
    struct  AvlNode
    {
        Comparable element;
        AvlNode * left;
        AvlNode * right;
        int height;

        AvlNode( const Comparable & _ele, AvlNode * lt , AvlNode * rt, int h = 0):
        element(_ele),left(lt),right(rt),height(h){}
        AvlNode( Comparable && _ele, AvlNode * lt , AvlNode * rt, int h = 0):
        element(std::move(_ele)),left(lt),right(rt),height(h){}
    };

    // The root of the tree
    AvlNode * root = nullptr;

    // return the height of node t & if t is a nullptr, return -1
    int height(AvlNode * t) const
    {
        return t == nullptr ? -1 : t->height;
    }
    void insert(const Comparable & _x, AvlNode * & t)
    {
        if(t==nullptr)
            t = new AvlNode(_x,nullptr,nullptr);
        else if(_x < t->element)
            insert(_x,t->left);
        else if(_x > t->element) 
            insert(_x,t->right);
        balance(t);
    }

    static const int ALLOWED_IMBALANCE = 1;
    // If the difference of height of node t's two subtrees, using methods of rotate to make it more balanced
    void balance(AvlNode * & t)
    {
        if( t== nullptr)
            return;
        if(height(t->left) - height(t->right) > ALLOWED_IMBALANCE)
            if(height(t->left->left) >= height(t->left->right) )
                rotateWithLeftChild(t);
            else
                doubleWithLeftChild(t);
        else if(height(t->right) - height(t->left) > ALLOWED_IMBALANCE)
        {
            if(height(t->right->right) >= height(t->right->left))
            {
                rotateWithRightChild(t);
            }
            else 
            {
                doubleWithRightChild(t);
            }
        }
        t->height = std::max(height(t->left),height(t->right))+1;
    }
    void rotateWithLeftChild(AvlNode * & k2)
    {
        AvlNode *k1 = k2->left;
        k2->left = k1->right;
        k1->right = k2;
        k2 -> height = std::max(height(k2->left),height(k2->right))  + 1;
        k1 -> height = std::max(height(k1->left),k2->height) +1;
        k2 = k1; 
    }
    void rotateWithRightChild(AvlNode * & k2)
    {
        AvlNode *k1 = k2->right;
        k2->right = k1->left;
        k1->left = k2;
        k2 -> height = std::max(height(k2->left),height(k2->right))  + 1;
        k1 -> height = std::max(height(k1->right),k2->height) +1;
        k2 = k1; 
    }

    void doubleWithLeftChild(AvlNode * & k3)
    {
        rotateWithRightChild(k3 -> left);
        rotateWithLeftChild(k3);
    }

    void doubleWithRightChild(AvlNode * & k3)
    {
        rotateWithLeftChild(k3 -> right);
        rotateWithRightChild(k3);
    }
    AvlNode * findMin(AvlNode * t) const
    {
        if(t==nullptr)
            return nullptr;
        if(t->right == nullptr)
            return t;
        return findMax (t->right);
        
    }

    void remove(const Comparable & x, AvlNode * & t)
    {
        if(t == nullptr)
            return;
        
        if(x < t->element)
            remove(x,t->left);
        else if(t->element < x)
            remove(x,t->right);
        else if(t->left != nullptr && t->right != nullptr)
        {
            t->element = findMin(t->right) -> element;
            remove(t->element,t->right);
        }
        else
        {
            AvlNode *oldNode = t;
            t= (t->left != nullptr) ? t->left : t->right;
            delete oldNode;
        }
    }
    // print out all elements with inorder traversal.

    void printout(AvlNode * t)
    {
        if(t==nullptr)
            return ;
        printout(t->left);
        std::cout << t->element << " ";
        printout(t->right);
    };

    public:
    void insert(const Comparable & x)
    {
        insert(x,root);
    }
    void insert(Comparable && x)
    {
        insert(std::move(x),root);
    }
    void printout()
    {
        printout(root);
        std::cout << std::endl;
    }
    // Return the height of the tree, i.e. height of root

    int height()
    {
        return height(root);
    }

};

template<typename Comparable>
class SplayTree
{
    private:
    // The splay node is similar to AvlNode, but because the splay tree needs the father of the node, SplayNode has new member father.
    struct  SplayNode 
    {
        Comparable element;
        SplayNode* left;
        SplayNode* right;
        SplayNode* father;
        int height;

        SplayNode ( const Comparable & _ele, SplayNode * lt , SplayNode  * rt,  SplayNode* father, int h = 0):
        element(_ele),left(lt),right(rt),height(h){}
        SplayNode ( Comparable && _ele, SplayNode  * lt , SplayNode  * rt,  SplayNode* father, int h = 0):
        element(std::move(_ele)),left(lt),right(rt),height(h){}
    };

   SplayNode  * root = nullptr;

    // return the height of node t & if t is a nullptr, return -1
    int height(SplayNode* t) const
    {
        return t == nullptr ? -1 : t->height;
    }
    // Inner function to insert an element to the tree
    void insert(const Comparable & _x, SplayNode* & t)
    {
        if(t==nullptr)
        {
            t = new SplayNode(_x,nullptr,nullptr,nullptr);
            t->height = 0;
        }
        else if(_x < t->element)
        {
            insert(_x,t->left);
            t->left->father = t;
        }
        else if(_x > t->element) 
        {
            insert(_x,t->right);
            t->right->father = t;
        }
        t->height = std::max(height(t->left),height(t->right))+1;
    }

    static const int ALLOWED_IMBALANCE = 1;
    // Rotate the given node t to the top of tree or the son of the top by rules of Splay tree
    void RotatetoTop(SplayNode* & t)
    {
        if (t == nullptr)
            return;        
        // If t's father is null, it is the root of the tree
        while(t ->father != nullptr )
        { 
            // obtain the father and grandfather
            SplayNode * & father = t->father;
            SplayNode * & grandfather = t->father->father;
            if(grandfather == nullptr)
            {
                return;
            }
            t->father = grandfather;
            // zig-zig case
            if(t->element < father->element && father->element < grandfather->element)
            {
                father -> left = t->right;
                if(t->right != nullptr)
                    t->right->father = father;
                t->right = father;
                father->father = t;
                father->height = std::max(height(father->left),height(father->right))+1;
                t->height =  std::max(height(t->left),height(t->right))+1;
                if(grandfather!=nullptr)
                    grandfather->left = t;
                if(grandfather!=nullptr)
                    grandfather->height =  std::max(height(t->left),height(t->right))+1;
            }
            // zig-zag case 
            else if(t->element > father->element && father->element < grandfather->element)
            {
                father -> right = t-> left;
                if(t->left != nullptr)
                    t->left->father = father;
                t->left = father;
                father->father = t;
                father->height = std::max(height(father->left),height(father->right))+1;
                t->height =  std::max(height(t->left),height(t->right))+1;
                if(grandfather!=nullptr)
                    grandfather->left = t;
                if(grandfather!=nullptr)
                    grandfather->height =  std::max(height(t->left),height(t->right))+1;
            }
            // zag-zag case
            else if(t->element > father->element && father->element > grandfather->element)
            {
                father -> right = t-> left;
                if(t->left != nullptr)
                    t->left->father = father;
                t->left = father;
                father->father = t;
                father->height = std::max(height(father->left),height(father->right))+1;
                t->height =  std::max(height(t->left),height(t->right))+1;
                if(grandfather!=nullptr)
                    grandfather->right = t;
                if(grandfather!=nullptr)
                    grandfather->height =  std::max(height(t->left),height(t->right))+1;
            }
             // zag-zig case
            else if(t->element < father->element && father->element > grandfather->element)
            {
                father ->left = t-> right;
                if(t->right != nullptr)
                    t->right->father = father;
                t->right = father;
                father->father = t;
                father->height = std::max(height(father->left),height(father->right))+1;
                t->height =  std::max(height(t->left),height(t->right))+1;
                if(grandfather!=nullptr)
                    grandfather->right = t;
                if(grandfather!=nullptr)
                    grandfather->height =  std::max(height(t->left),height(t->right))+1;
            }
        }
    }

    SplayNode * findMin(SplayNode * t) const
    {
        if(t==nullptr)
            return nullptr;
        if(t->right == nullptr)
            return t;
        return findMax (t->right);
        
    }
    // Inner function to delete one of the element of tree
    void remove(const Comparable & x, SplayNode* & t)
    {
        if(t == nullptr)
            return;
        
        if(x < t->element)
            remove(x,t->left);
        else if(t->element < x)
            remove(x,t->right);
        else if(t->left != nullptr && t->right != nullptr)
        {
            t->element = findMin(t->right) -> element;
            remove(t->element,t->right);
        }
        else
        {
            SplayNode*oldNode = t;
            t= (t->left != nullptr) ? t->left : t->right;
            delete oldNode;
        }
    }

    // print out all elements with inorder traversal. As long as the element is read
    void printout(SplayNode* t)
    {
        if(t==nullptr)
            return ;
        printout(t->left);
        std::cout << t->element;
        RotatetoTop(t);
        printout(t->right);
    };

    public:
    // add element to the tree
    void insert(const Comparable & x)
    {
        insert(x,root);
    }
    void insert(Comparable && x)
    {
        insert(std::move(x),root);
    }
    // print the tree using inoder traversal
    void printout()
    {
        printout(root);
        std::cout << std::endl;
    }
    // return the height of whole tree
    int height()
    {
        return height(root);
    }

};
